#include <limits.h>
#include "main/utils.h"
using namespace std;

vector<int> maxValInSlipWindows(const vector<int> &vec, const int &k) {
  if (!(vec.size() >= k && k >= 1))
    return {};
  vector<int> ret;
  int max = INT_MIN;
  int max_idx = -1;
  for (int i = 0; i < k; ++i) {
    if (vec[i] > max) {
      max = vec[i];
      max_idx = i;
    }
  }

  deque<int> help_deque;
  help_deque.push_back(max_idx);
  ret.push_back(max);
  for (size_t i = k; i < vec.size(); ++i) {
    auto deque_begin = help_deque.front();
    if (i - deque_begin >= k) {
      help_deque.pop_front();
    }
    while (!help_deque.empty() && vec[i] >= vec[help_deque.back()]) {
      help_deque.pop_back();
    } 
    help_deque.push_back(i);
    ret.push_back(vec[help_deque.front()]);
  }
  return ret;
}

class DefineDequeWithMax {
  public:
    DefineDequeWithMax() : cur_idx(0) {};

    void push_back(const int &num) {
      deque_data.push_back({num, cur_idx});
      while (!deque_max.empty() && deque_max.back().data < num) {
        deque_max.pop_front();
      }
      deque_max.push_back({num, cur_idx});
      ++cur_idx;
    }

    void pop_front() {
      if (deque_data.empty() || deque_max.empty()) {
        cout << "Error when pop_front" << endl;
      }
      if (deque_max.front().idx == deque_data.front().idx) {
        deque_max.pop_front();
      }
      cout << "pop front " << deque_data.front().data << endl;
      deque_data.pop_front();
    }

    int max() const {
      int ret = -1;
      if (!deque_max.empty()) {
        ret = deque_max.front().data;
      }
      return ret;
    }

  private:
    struct InterData {
      int data;
      int idx;
    };

    deque<InterData> deque_data;
    deque<InterData> deque_max;
    int cur_idx;
};

int main() {
  vector<int> vec = {2, 3, 4, 2, 6, 2, 5, 1};
  int k = 3;
  vector<int> maxs = maxValInSlipWindows(vec, k);
  printVec("maxValInSlipWindows", maxs);

  DefineDequeWithMax max_deque;
  max_deque.push_back(2);
  max_deque.push_back(3);
  cout << max_deque.max() << " expect: 3" << endl;
  max_deque.push_back(4);
  cout << max_deque.max() << " expect: 4" << endl;
  max_deque.pop_front();
  max_deque.push_back(2);
  cout << max_deque.max() << " expect: 4" << endl;
  max_deque.pop_front();
  max_deque.pop_front();
  cout << max_deque.max() << " expect: 2" << endl;

  return 0;
}
